﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.DataStructures.Digraphs;
using Algoritmia.DataStructures.Maps;
using Algoritmia.Problems.Traversals;
using Algoritmia.Utils;
using Algoritmia.Utils.Backtracers;

namespace Algoritmia.Problems.ShortestPaths.Length
{
    public class BreadthFirstShortestPathsFinder<T> : IShortestPathsFinder<T,int>
    {
        private readonly Func<IEnumerable<T>, IMap<T, int>> _createMap;
        private readonly Func<IEnumerable<T>, IGraphBreadthFirstTraverser<T, Tuple<T,T>>> _createBreadthFirstTraverser;
        private readonly EqualityComparison<T> _equalityComparison;
        private readonly Func<IEnumerable<T>, IMap<T, T>> _createBackpointersMap;

        public BreadthFirstShortestPathsFinder(Func<IEnumerable<T>,IMap<T,int>> createMap = null,
                                               Func<IEnumerable<T>,IMap<T,T>> createBackpointersMap = null,
                                               Func<IEnumerable<T>,IGraphBreadthFirstTraverser<T,Tuple<T,T>>> createBreadthFirstTraverser = null,
                                               EqualityComparison<T> equalityComparison = null)
        {
            _createMap = createMap ?? ( it => AlgoritmiaFactory.Maps<T,int>.Default );
            _createBackpointersMap = createBackpointersMap ?? (it => AlgoritmiaFactory.Maps<T, T>.Default);
            _createBreadthFirstTraverser = createBreadthFirstTraverser ?? (it => new BreadthFirstTraverser<T, Tuple<T,T>>());
            _equalityComparison = AlgoritmiaFactory.GetDefaultEqualityComparison(equalityComparison);
        }

        public int Distance(IDigraph<T> g, T source, T target)
        {
            var length = _createMap(g.V);
            length[source] = 0;
            var breadthFirstTraverser = _createBreadthFirstTraverser(g.V);
            foreach(var edge in breadthFirstTraverser.Traverse(g,source,(u,v) => new Tuple<T, T>(u,v)))
            {
                if ( !_equalityComparison(edge.Item1,edge.Item2))
                {
                    length[edge.Item2] = length[edge.Item1] + 1;
                }
                if (_equalityComparison(edge.Item2, target))
                    return length[target];
            }
            return -1;
        }

        public IEnumerable<T> ShortestPath(IDigraph<T> g, T source, T target)
        {
            var backpointers = _createBackpointersMap(g.V);
            var breadthFirstTraverser = _createBreadthFirstTraverser(g.V);
            foreach(var edge in breadthFirstTraverser.Traverse(g,source,( (u,v) => new Tuple<T, T>(u,v))))
            {
                backpointers[edge.Item2] = edge.Item1;
                if ( _equalityComparison(edge.Item2,target))
                {
                    break;
                }
            }
            return new Backtracer<T>(backpointers).Backtrace(target);
        }

        public IEnumerable<KeyValuePair<T,T>> OneToAllBackpointers(IDigraph<T> g, T source)
        {
            var bft = _createBreadthFirstTraverser(g.V);
            return from tuple in bft.Traverse(g, source, (u, v) => new Tuple<T, T>(v, u))
                   select new KeyValuePair<T, T>(tuple.Item1, tuple.Item2);
        }

        #region IShortestPathFinder<T,int> members

        public IEnumerable<KeyValuePair<T, T>> SomeToSomeBackpointers(IDigraph<T> g, WeightingFunction<T,int> d, IEnumerable<T> sources, IEnumerable<T> targets)
        {
            var traverser = _createBreadthFirstTraverser(g.V);
            var targetsList = targets.ToList();
            int left = targetsList.Count;

            foreach (var edge in traverser.TraverseFromSome(g, sources, (u, v) => new Tuple<T, T>(u, v)))
            {
                yield return new KeyValuePair<T, T>(edge.Item2, edge.Item1);
                if ( targetsList.Contains(edge.Item2))
                {
                    left--;
                    if ( left == 0)
                    {
                        break;
                    }
                } 
            }
        }

        public int SomeToSomeDistance(IDigraph<T> g, WeightingFunction<T, int> d, IEnumerable<T> sources, IEnumerable<T> targets)
        {
            var length = _createMap(g.V);
            var traverser = _createBreadthFirstTraverser(g.V);
            var sourcesList = sources.ToList();

            foreach (var s in sourcesList)
            {
                length[s] = 0;
            }

            foreach (var edge in traverser.TraverseFromSome(g, sourcesList, (u, v) => new Tuple<T, T>(v, u)))
            {
                if (!_equalityComparison(edge.Item1, edge.Item2))
                {
                    length[edge.Item1] = length[edge.Item2] + 1;
                }
            }
            return targets.Min(t => length[t]);
        }

        #endregion
    }
}
